1. Technical Field of the Invention
This invention relates to a method and apparatus for parallel simulation of integrated circuits. More particularly, it relates to the use of a global virtual time in the simulation for garbage collection.
2. Background Art
Previously known logic simulators assist in the design, development and debugging of complex circuitry. For example, the logic simulator may determine if a proposed circuit design performs the requisite function and meets other specifications before the circuitry is built. The simulator can simulate digital logic and even analog circuitry. Each logic simulator comprises one or more computer programs and data structures to simulate the circuitry. For each logic component, such as an AND gate, the logic simulator program includes a subroutine which performs a logical AND operation and maintains a data structure which stores the inputs and resultant outputs. The computer program can also supply some or all of the digital input signals to the simulated circuit, to initiate operation of the simulated circuit. The digital input signals simulate electronic signals that would be supplied by other circuitry or programming associated with the simulated circuit.
In time-warp parallel simulation, processor nodes communicate with each other by sending messages. Jefferson describes the use, for garbage collection, of periodically calculating the global virtual time (GVT) of the simulation. See D. R. Jefferson, "Virtual time," in ACM Transactions on Programming Languages and Systems, pp. 404-425, July 1985. Garbage collection refers to the reclaiming of storage used for executed messages with time stamp earlier than GVT. GVT at real time t is the minimum of all local clocks at real time t, and of the timestamps of all transient messages at real time t. Thus, the calculation of GVT requires the calculation of the least time-stamp of all in-transit messages.
Lin and Lazowska describe a method for determining the in-transit message with the least time stamp of two communicating processes. See Y. B. Lin and E. D. Lazowska, "Determining the global virtual time in a distributed simulation," in Proc. International Conference on Parallel Processing, pp. 201-209, 1990. Each message that is sent from one process to another is labeled with a sequence number and a time stamp, where the time stamp indicates the simulation time of the event in the message. In accordance with the system and method described by Lin and Lazowska, supra, an output trail buffer (OTB) on the sending process, and an input trail buffer (ITB) on the receiving process is used to record these sequence numbers and time stamps of messages. The ITB records the sequence number and time stamp of the most recently received message. The OTB contains a list of all "valley" messages that have been sent, where a valley message is defined as a message with a time stamp that is less than the time stamp of the previously sent message. During the GVT calculation each ITB sends the last received time stamp and sequence number to its corresponding OTB. The OTB then compares this information against its valley messages and determines the in-transit message with the least time stamp.
The time and complexity of this method grows as a function of O(p.sup.2), where p is the number of simulation processes. ("O" is the "order" or "Big O" notation used by computer scientists. It is a way to measure relative performance between algorithms. O(p.sup.2) means that, if the execution time equation for the algorithm were completely determined, the largest power component would be "p.sup.2 ", so this would dominate the equation result, in this case execution time.) This method is, therefore, effective when only a few processes reside on each processor and the total number of processes is relatively close to the number of processors in the simulation.
In VHDL, however, a large number of simulation processes can occur on a single processor, and the in-transit message detection method incurs a high computational and memory cost. (VHDL refers to the VHSIC Hardware Description Language of IEEE standard 1076, where VHSIC means "very high speed integrated circuit.")
In accordance with one approach for avoiding the complexity of the method presented by Lin and Lazowska, one OTB-ITB pair is assigned per processor pair. In the worst case scenario, every processor communicates with all other processors and the number of OTB-ITB pairs is n.sup.2, where n is the number of processors. The number of messages required for determining all in-transit messages is equal to the number of ITBs and is, therefore, also bounded by n.sup.2. Since one OTB-ITB pair is assigned to each processor pair, multiple processes on a processor will send messages through one OTB-ITB pair. This creates what is referred to as the "false-valley" problem. Each process on a processor maintains its own local simulation time. If two processes alternately send messages through one OTB, it will appear to that OTB that every other message is a valley, since it is sent by different processors with a different local time. The false-valley problem drastically increases the length of the valley list in an OTB thereby increasing the memory and processing requirement of the method.
The direct implementation of an in-transit message detection method assigns one OTB-ITB pair to each pair of communicating processes. This way, an OTB processes messages sent by a single simulation process and will not generate false valleys. However, the number of OTB-ITB pairs and the number of message sent during the GVT calculation are now bounded by p.sup.2, where p is the number of processes in the parallel simulation. The number of simulation processes can be significantly higher than the number of processors. Since the memory and processing costs grow as O(p.sup.2), where p is the number of simulation processes, this method also incurs a high space and time penalty.
It is, therefore, an object of the invention to provide a system and a method for determining the in-transit message with the least time stamp which does not incur a high memory or computational cost.
It is also an object of the invention to provide such a system and method which further eliminates the false-valley problem.
It is a further object of the invention to provide a method for determining in-transit messages that eliminate the false-valley problem and requires at most n.sup.2 messages, where n is the number of processors.